| 面试必备：四种经典限流算法讲解 | 您所在的位置：网站首页 › redisson 限流 › 面试必备：四种经典限流算法讲解 |
面试必备：四种经典限流算法讲解
|
前言
大家好,我是田螺. 最近一位朋友去拼夕夕面试,被问了这么一道题:限流算法有哪些?用代码实现令牌桶算法。跟星球好友讨论了一波,发现大家都忘记得差不多了.所以田螺哥再整理一波，常见的四种限流算法,以及简单代码实现,相信大家看完,会茅塞顿开的。 固定窗口限流算法（Fixed Window Rate Limiting Algorithm）是一种最简单的限流算法，其原理是在固定时间窗口(单位时间)内限制请求的数量。该算法将时间分成固定的窗口，并在每个窗口内限制请求的数量。具体来说，算法将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出了限制，则拒绝该请求。 假设单位时间(固定时间窗口)是1秒，限流阀值为3。在单位时间1秒内，每来一个请求,计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。等到1s结束后，计数器清0，重新开始计数。如下图： 
1.2 固定窗口限流的伪代码
public static Integer counter = 0; //统计请求数 public static long lastAcquireTime = 0L; public static final Long windowUnit = 1000L ; //假设固定时间窗口是1000ms public static final Integer threshold = 10; // 窗口阀值是10 /** * 固定窗口时间算法 * 关注公众号：捡田螺的小男孩 * @return */ public synchronized boolean fixedWindowsTryAcquire() { long currentTime = System.currentTimeMillis(); //获取系统当前时间 if (currentTime - lastAcquireTime > windowUnit) { //检查是否在时间窗口内 counter = 0; // 计数器清0 lastAcquireTime = currentTime; //开启新的时间窗口 } if (counter = thresholdPerMin) { return false; } //计数器+1 counters.get(currentWindowTime)++; return true; } /** * 统计当前窗口的请求数 */ private int countCurrentWindow(long currentWindowTime) { //计算窗口开始位置 long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1); int count = 0; //遍历存储的计数器 Iterator iterator = counters.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry entry = iterator.next(); // 删除无效过期的子窗口计数器 if (entry.getKey() 0) { tokens--; return true; } else { return false; } } /** * refill() 方法用于生成令牌，其中计算令牌数量的逻辑是按照令牌生成速率每秒钟生成一定数量的令牌， * tokens 变量表示当前令牌数量， * lastRefillTimestamp 变量表示上次令牌生成的时间戳。 */ private void refill() { long now = System.currentTimeMillis(); if (now > lastRefillTimestamp) { int generatedTokens = (int) ((now - lastRefillTimestamp) / 1000 * rate); tokens = Math.min(tokens + generatedTokens, capacity); lastRefillTimestamp = now; } }}
4.3 令牌桶算法的优缺点
优点： 稳定性高：令牌桶算法可以控制请求的处理速度，可以使系统的负载变得稳定。 精度高：令牌桶算法可以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流。 弹性好：令牌桶算法可以处理突发流量，可以在短时间内提供更多的处理能力，以处理突发流量。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。 缺点： 实现复杂：相对于固定窗口算法等其他限流算法，令牌桶算法的实现较为复杂。对短时请求难以处理：在短时间内有大量请求到来时，可能会导致令牌桶中的令牌被快速消耗完，从而限流。这种情况下，可以考虑使用漏桶算法。 时间精度要求高：令牌桶算法需要在固定的时间间隔内生成令牌，因此要求时间精度较高，如果系统时间不准确，可能会导致限流效果不理想。总体来说，令牌桶算法具有较高的稳定性和精度，但实现相对复杂，适用于对稳定性和精度要求较高的场景。 |
【本文地址】
公司简介
联系我们